package temp.leetcode.editor.cn;

//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。
//
// 示例 2：
//
//
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 100
//
//
// Related Topics 数组 动态规划 👍 1704 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 分割等和子集
 *
 * @author saint
 */
class P416_PartitionEqualSubsetSum{
    public static void main(String[] args) {
        Solution solution = new P416_PartitionEqualSubsetSum().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

        //背包问题是 回溯法子集问题的优化解法
    public boolean canPartition(int[] nums) {
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if (sum%2 == 1){
            return false;
        }
        int target = sum/2;
        //01背包问题dp[i][j]表示容量为j的背包从 0-i的物品里任意取，放进背包的最大价值和
//        int[][] dp = new int[nums.length][target+1];
//       //初始化第一行和第一列
//        for (int j = nums[0]; j <= target ; j++) {
//            dp[0][j] = nums[0];
//        }
//        for (int i = 0; i < nums.length; i++) {
//            dp[i][0] = 0;
//        }
//        for (int i = 1; i < nums.length; i++) {
//            for (int j = 0; j <= target; j++) {
//                //不拿 dp[i-1][j]  拿dp[i-1][j-nums[i]]+nums[i];
//                if (j-nums[i]<0){
//                    dp[i][j] = dp[i-1][j];
//                }else{
//                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
//                }
//            }
//        }
//        for (int i = 0; i < nums.length; i++) {
//            if (dp[i][target] == target) {
//                return true;
//            }
//        }
        //使用滚动数组作为动态规划dp数组
        //dp[j]表示容量为j时的最大价值
        int[] dp = new int[target+1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i] ; j--) {
                //顺序为从后往前，没有更新的dp为上一个物品的dp,也就是根据左上来更新，和二维数组一样
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
            for (int j = 0; j <= target; j++) {
                System.out.print( + dp[j]+" ");
            }
            System.out.println("");

        }
        if (dp[target] == target){
            return true;
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
